package code;

import java.util.Scanner;

public class 剑指offer10_I {
    static int[] dp=new int[105];
    final static int MOD= (int) (1e9+7);
    public int fib1(int n) {
        /***
         * 1、使用记忆化搜索进行保存查询的结果
         * 时间复杂度：O（fib（n-2））和斐波那契数列一致
         * 空间复杂度：O（n）
         */
        if(n<2){
            return dp[n]=n;
        }
        int f1=(dp[n-1]>0)?dp[n-1]:fib1(n-1);
        int f2=(dp[n-2]>0)?dp[n-2]:fib1(n-2);
        dp[n]=(f1%MOD+f2%MOD)%MOD;
        return dp[n];
    }
    static {
        dp[0]=0;dp[1]=1;
        for(int i=2;i<101;++i)dp[i]=(dp[i-1]%MOD+dp[i-2]%MOD)%MOD;
    }
    public int fib2(int n) {
        /***
         *2、使用动态规划求解
         * 时间复杂度：O（n）
         * 空间复杂度：O（n）
         */
        return dp[n];


    }
    int[] DP=new int [3];
    public int fib3(int n) {
        /***
         * 3、使用长度为3的数组
         */
        DP[0]=0;DP[1]=1;
        for(int i=2;i<=n;++i){
            DP[i%3]=(DP[(i-1)%3]%MOD+DP[(i-2)%3]%MOD)%MOD;
        }
        return DP[n%3];
    }

    public int fib(int n) {
        int a = 0, b = 1, sum;
        for(int i = 0; i < n; i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
    public static void main(String[] args) {

    }
}
